# -*- coding: utf-8 -*-
"""
    Time    : 2020/12/21 11:09 下午
    Author  : Thinkgamer
    File    : 076-最小覆盖子串.py
    Desc    : https://leetcode-cn.com/problems/minimum-window-substring/
"""

"""
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：
输入：s = "a", t = "a"
输出："a"

提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
"""

"""
	v1: 最小覆盖子串的长度为 字符串 t 的长度，最大为 s的长度，因此 可以分别遍历 两个长度之间的滑动窗口在字符串 s 上的子串，看是否包括 t
		运行超时
	v2: 基于v1进行优化, 思路相同，只是在进行是否包含时进行了优化判断
		运行超时
	v3: 参考题解：https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
		定义两个指针 left、right；定义最小子串的左侧开始下标；定义最小子串的长度
		right 每次往右移动一格，直到当前子串s[left:right] 包含t时，尝试将 左指针 left 右移，在不影响全部包含 t 的情况下，left 往左移动，当不满足最小子串条件时，right 往右移动，如此往复
		提交通过
"""


def min_window_v1(s, t):
	# 采用滑动窗口的思路，包含t 的最小覆盖字串应该是 t的长度，依次进行累加
	for min_len in range(len(t), len(s)+1):
		# print("min_len: {}".format(min_len))
		# 每次指定最小覆盖字串长度时，从0开始进行遍历
		start_index = 0
		while start_index <= len(s) - min_len:
			# print("start_index: {}".format(start_index))
			# 记录 t 中字符是否在s中出现过
			flag_char = dict()
			for char in t:
				flag_char.setdefault(char, 0)
				flag_char[char] += 1
			for char in s[start_index:start_index+min_len]:
				if flag_char.keys().__contains__(char):
					flag_char[char] -= 1
					if flag_char[char] < 0:
						flag_char[char] = 0
					if sum(flag_char.values()) == 0:
						return s[start_index:start_index+min_len]
			start_index += 1
	return ""


def min_window_v2(s, t):
	from collections import Counter
	# 采用滑动窗口的思路，包含t 的最小覆盖字串应该是 t的长度，依次进行累加
	for min_len in range(len(t), len(s) + 1):
		# print("min_len: {}".format(min_len))
		# 每次指定最小覆盖字串长度时，从0开始进行遍历
		start_index = 0
		while start_index <= len(s) - min_len:
			# print("start_index: {}".format(start_index))
			s_dict = Counter(s[start_index:start_index + min_len])
			t_dict = Counter(t)
			flag = True
			for k in t_dict.keys():
				if s_dict[k] < t_dict[k]:
					flag = False
					break
			if flag:
				return s[start_index:start_index + min_len]
			start_index += 1
	return ""


def min_window_v3(s, t):
	# 先统计 t 中的字符情况
	char_count = dict()
	char_flag = dict()
	for char in t:
		char_count.setdefault(char, 0)
		char_count[char] += 1
		char_flag[char] = True

	# 滑动窗口
	left = 0
	min_left = 0
	min_len = len(s) + 1
	count = 0
	# right 指针 依次往右进行遍历，每次移动一格
	for right in range(len(s)):
		if char_flag.keys().__contains__(s[right]) and char_flag[s[right]]:
			char_count[s[right]] -= 1
			if char_count[s[right]] >= 0:
				count += 1

		# 若目前窗口中包括 t 中的全部字符，则将 左指针 left 往右移动一格，在不影响结果的情况下 获取最短子串
		while count == len(t):
			# 比较 当前子串长度 与 最小长度 的大小
			if right - left + 1 < min_len:
				min_len = right - left + 1
				min_left = left

			if char_flag.keys().__contains__(s[left]):
				char_count[s[left]] += 1
				if char_flag[s[left]] and char_count[s[left]] > 0:
					count -= 1
			left += 1
	if min_len <= len(s):
		return s[min_left: min_left + min_len]
	else:
		return ""

# s = "ADOBECODEBANC"
# t = "ABC"
# s = "a"
# t = "a"
# s = "bbaa"
# t = "aba"
# s = "aaaaaaaaaaaabbbbbcdd"
# t = "abcdd"
# s = "qxsncfwvbslazxuoxnedkukropehlwfbwxqycntdfgghecvdqbhcwtukkauwzzzvystcfohmupvastekunmqiidtjxriyqdyiyapohekxblrurbpgphoykjhjarhtwfduhvkpzumahdxagmivtxvgiepjvxetehnmczddurgdwdecrmzklxqubgfzfjslqizvheadvghrlnvcbxpnuhjxpqywzrkrbjokqpolxxflkapnzeatmltdbrackkwlvmwlbmxbjcmvebieilzwyszckzgulcihpgsssrtdvhaaligvvfrwaqyksegdjqmywfsoyotuxtwieefbjwxjpxvhcemnwzntgfjetdatyydecjgofdzudxbfbqsxpfsvmebijcbhcemfnuvtzupcrthujbuyiovvswdbagjdkxkyrftqbktvdcpogloqajlsgquiyfljcxjveengogbulsitexjeixwqpszoxkzzkiuooiweqxydqjywiiaqhyhwrgkosloetktjuponposfxrdhzdyibhesprjjczoyjhhgyxtnmlulextdatnecsyrlhangonsxxywutligguldpqgiemkymdjufycumwtjupfpdowjkjozzwjdivbvymrdlvzzstkmkpenfcyplnqkjzquutrsgiytdxsvsckftquzstqdihnrgfnbbevjovcutupnyburrpsjijmsqclyjzzk"
# t = "fxtusxonrfdrhxjamdkwm"
s = "eccdmbeygbucwrqllyocfmnhartzdspkwrnksrjbvdftwyehwtkdhxkjqeiwyyguptfkmqnjvscrqjzoelrnkcwbgfxgffawyhimzvwuqaoilpxpaqcksznagmglrjhrssesncofeeqqtphvfkiylvatijgbsptmhxgvbxcfbsvxjdsppapcypxiydjssefablxckbkmufjfkdubgjfebcozfzuaezafmzkxaulwbwcozwrhizljbbijbcjfdlmskwrkscjwalmzjdhrcuagwlpxpaevlqnvpehhiqfidrjnxsebnhhluykjyoglgvivbsfjiktoedbbxfemomximjunzaygwjdzbijlvezzjachigtwuthhcbwedumzfrbgaksxqryauahciaafthoyikemgqnmhosjamgrggtaiaeraewwmkwwwakcsaozqjltxtkdaddifhbhozdclbahblmtncvdngwlbiobnumsbparpftahwkkhwguabzojwzmenouhcmlroegwajdwvpdtvztyahjwgwdwmxfolqfcvoyxzbtusynozgozqywywbuiycwlsdnprlmqohmhfzxeineyncwjdtrdvpoptehmrvfgdrpiropzdtxrvvayqudljrdcxkrphwvknmvgckfffewaczastdgewjhuvajcwgnlukswwzdbgcdib"
t = "fawiiagr"
result = min_window_v3(s, t)
print(result)
